'''
Created on Jun 10, 2009

@author: sternron
'''
import unittest
from graph import graph

from cliques.knownDegreeSearch import knownDegreeSearch
from cliques.algorithmRunner import algorithmRunner

class test_probabilistic_search(unittest.TestCase):


    def testKnownDegree(self):
        # Create a graph designed to fool known degree
        # Goal: verify that known degree doesn't cheat and use all the graph
        test_graph = graph()
        nodes = ['n0','n1','n2','n3','n4','n5','n6','n7','n8']
        test_graph.add_node(nodes[0])
        test_graph.add_node(nodes[1])
        test_graph.add_node(nodes[2])
        test_graph.add_edge(nodes[0],nodes[1])
        test_graph.add_edge(nodes[0],nodes[2])
        test_graph.add_edge(nodes[1],nodes[2])
        test_graph.add_node(nodes[3])
        test_graph.add_node(nodes[4])
        test_graph.add_edge(nodes[1],nodes[3])
        test_graph.add_edge(nodes[2],nodes[4])
        test_graph.add_node(nodes[5])
        test_graph.add_node(nodes[6])
        test_graph.add_node(nodes[7])
        test_graph.add_node(nodes[8])
        test_graph.add_edge(nodes[3],nodes[5])
        test_graph.add_edge(nodes[3],nodes[6])
        test_graph.add_edge(nodes[3],nodes[7])
        test_graph.add_edge(nodes[3],nodes[8])
        test_graph.add_edge(nodes[4],nodes[5])
        test_graph.add_edge(nodes[4],nodes[6])
        test_graph.add_edge(nodes[4],nodes[7])
        test_graph.add_edge(nodes[4],nodes[8])        
        test_graph.add_edge(nodes[5],nodes[6])
        test_graph.add_edge(nodes[5],nodes[7])
        test_graph.add_edge(nodes[5],nodes[8])
        test_graph.add_edge(nodes[6],nodes[7])
        test_graph.add_edge(nodes[6],nodes[8])
        test_graph.add_edge(nodes[7],nodes[8])
        
        # Run
        algo = knownDegreeSearch()
        algo.setup(test_graph, 5, nodes[0])
        
        # Take 2 steps, verify nodes 0,1 and 2 have been chosen
        assert nodes[0] in algo.expanded
        assert algo.halt()==False
        algo.step()
        algo.status()
        assert algo.halt()==False      
        algo.step()
        algo.status()        
        assert algo.halt()==False
        assert nodes[1] in algo.expanded
        assert nodes[2] in algo.expanded
        
        # Check clique is found eventually
        runner = algorithmRunner()
        runner.run(algo)
        assert algo.done
        observed_clique = algo.output_clique()
        assert nodes[5] in observed_clique
        assert nodes[6] in observed_clique
        assert nodes[7] in observed_clique
        assert nodes[8] in observed_clique


if __name__ == "__main__":
    #import sys;sys.argv = ['', 'Test.testKnownDegree']
    unittest.main()